# 752. 打开转盘锁
# 有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
#
# 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
#
# 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
#
# 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

from typing import List
import queue

class staModel:
    def __init__(self,level,status):
        self._level = level
        self._status = status

class Solution:
    def __init__(self):
        self._curStr = "0000"
        self._deadend = [[[[0 for i in range(10)]for j in range(10)]for k in range(10)] for l in range(10)]
        self._visited = [[[[0 for i in range(10)]for j in range(10)]for k in range(10)] for l in range(10)]
    def upup(self,num:int):
        if num < 9:
            return num+1
        if num == 9:
            return 0

    def downdown(self,num:int):
        if num>0:
            return num-1
        if num== 0:
            return 9



    def openLock(self, deadends: List[str], target: str) -> int:
        if target == '0000':
            return 0



        if '0000' in deadends:
            return -1

        for num in deadends:
            self._deadend[int(num[0])][int(num[1])][int(num[2])][int(num[3])] = 1

        q = queue.Queue()
        initModel = staModel(0,'0000')
        self._visited[0][0][0][0] = 1
        q.put(initModel)
        while q.empty() is False:
            # print("q")
            model = q.get()
            level = model._level
            status = model._status
            for i,c in enumerate(status):
                for j in range(2):
                    newC = ''
                    if j %2 ==0:
                        newC = self.upup(int(c))
                    else:
                        newC = self.downdown(int(c))
                    newStatus = status[0:i] + str(newC) + status[i+1:]


                    if self._deadend[int(newStatus[0])][int(newStatus[1])][int(newStatus[2])][int(newStatus[3])] == 1:
                        continue

                    if self._visited[int(newStatus[0])][int(newStatus[1])][int(newStatus[2])][int(newStatus[3])] == 1:
                        continue

                    else:
                        print(newStatus)
                        if newStatus == target:
                            return level+1
                        newModel = staModel(level+1,newStatus)
                        print(level+1)
                        q.put(newModel)
                        self._visited[int(newStatus[0])][int(newStatus[1])][int(newStatus[2])][int(newStatus[3])] = 1


        return -1

# qq = queue.Queue()
#
# qq.put(3)
# qq.get()
# print(qq.empty())
#
#
# asd= "asdfg"
# print(asd[6:])
# for i,c in enumerate(asd):
#     print(i,c)

res = Solution().openLock(["6876","8767","7678","7767","8767","7786","6877","6768","6686","6688","7778","6866","7777","7776","7678","7877","8887","7766","8786","8667","6887","7878","8868","7776","8867","6768","8878","7878","6777","8767","6686","8767","7688","7866","6778","7887","6876","8778","6687","8777","8767","7766","7786","8786","7678","8777","8776","8886","6888","8688","7888","8687","7787","7867","8886","7777","6768","6676","8766","8767","7668","8787","6877","8687","6678","7688","7767","6887","8766","8867","8687","8767","8878","6678","8678","6666","7786","8668","8867","6667","7887","6686","7687","8876","8866","6678","6766","6867","6786","7777","6666","8877","7676","7766","6868","6867","6888","7877","7778","7877","7867","6688","7887","7677","6678","8776","8787","7867","6686","7676","6678","6677","6678","7767","6677","7687","7867","7767","6678","7666","7867","8668","6666","8677","6867","7677","7686","8686","7676","8778","7686","8787","6687","7867","7687","6767","8786","6877","7886","6786","8778","6887","7776","7778","8766","7767","7888","6688","8866","8678","7868","7766","8876","8787","7768","8866","6866","7787","7676","8886","6868","7888","8678","6888","8666","8866","8887","6686","7667","6787","8677","7867","6776","8868","7668","6767","6676","6666","7887","7786","8687","7778","7776","8887","6786","6888","6666","8788","7768","6877","6676","8788","7888","7888","6678","6767","8668","7776","7667","7767","8686","7877","6787","7888","8788","7776","7678","8666","8868","7868","6776","8776","6666","7788","7876","8676","6767","8787","6777","6887","8877","6666","8877","7766","6887","8887","7888","6887","7666","6676","6788","6788","6778","8688","7676","7688","7767","8868","7786","6778","6687","7768","7878","8778","7678","7687","7768","8787","7666","7878","8767","7676","8768","6667","6766","6686","7678","8687","7687","8678","6766","6776","8766","6888","6678","6776","8676","8677","6788","8666","7866","6677","6877","7767","7786","8788","7686","6777","7868","8787","6678","6886","8886","8868","6888","8678","7778","6768","8776","8776","8787","6667","6767","8688","6686","7676","6887","7876","6886","7676","6876","6676","8688","6688","7787","6668","8788","6877","6876","7878","6677","7678","7768","8776","7877","6867","7776","7766","6676","8767","8686","8766","7788","6786","7888","7677","7868","8766","8767","6867","6668","8866","6788","8776","7868","6676","7866","7766","6888","8787","7876","8888","8878","7768","7788","7666","7787","6886","6768","8767","8688","6778","7767","7677","7886","8867","6867","6866","7676","7886","7886","8676","7688","7666","7878","6866","8667","8787","7767","7877","8666","7667","6676","7767","7886","7667","8766","8766","7787","6777","7777","6888","6776","6666","8767","6768","6667","6867","6666","6788","7677","8877","7687","7878","6678","6777","6777","7666","7686","6678","7787","7678","8688","7767","7877","7668","6676","6868","6777","6886","7776","6687","8688","6686","8688","8878","8868","8778","6686","6866","8686","8776","8868","8777","8876","6667","6766","8766","7668","8886","6788","6888","7888","7668","8676","6676","6778","7687","8866","8866","7666","8668","8766","7867","7888","8677","8778","6667","6678","6678","7778","8887","8786","8867","7887","6766","8787","6676","7667","6666","8666","6888","7788","6767","8666","7877","6786","7688","7676","7668","6876","6868","7877","7677","7678","6866","7787","6787","7888","8788","6668","6788","6768","8878","7667","8786","6877","8787","7766","7788","7788","8888","8867","6876","6776","6688","6668","6868","7787","8877"],
"6878")

print(res)
